package com.sourcetrip.algorithm.unionfind;

import com.sourcetrip.algorithm.inter.UnionFindCustomedObject;

import java.util.HashMap;
import java.util.Objects;

/**
 * @author: ZhouBert
 * @date: 2021/1/8
 * @description: 并查集对象比较版本（Quick Union ）
 * 设计：
 * 1.使用 HashMap 替代 原先的 数组
 * 2.使用 Path Compression 和 rank 进行优化
 */
public class UnionFindCustomedObjectWithQuickUnion<E> implements UnionFindCustomedObject<E> {

	/**
	 * 存储并查集元素
	 */
	private HashMap<E, Node<E>> parents = new HashMap<>();


	/**
	 * 查找元素
	 * Path Compression
	 * @param ele
	 * @return
	 */
	@Override
	public E find(E ele) {
		if (!parents.containsKey(ele)) {
			//throw new IllegalArgumentException(ele + ":element not found!");
			return ele;
		}
		Node<E> node = node(ele);
		return node.value;
	}

	/**
	 * 合并两个元素
	 *
	 * @param e1
	 * @param e2
	 */
	@Override
	public void union(E e1, E e2) {
		//如果并查集里没有，就进行创建
		makeSet(e1);
		makeSet(e2);

		E r1 = find(e1);
		E r2 = find(e2);
		if (Objects.equals(r1, r2)) {
			return;
		}
		Node<E> r1Node = parents.get(r1);
		Node<E> r2Node = parents.get(r2);
		if (r1Node.rank == r2Node.rank) {
			//嫁接到 r2
			r2Node.rank++;
			r1Node.parentNode = r2Node;
		} else if (r1Node.rank > r2Node.rank) {
			//小的嫁接到大的
			r2Node.parentNode = r1Node;
		} else {
			r1Node.parentNode = r2Node;
		}

	}

	@Override
	public boolean isSame(E e1, E e2) {
		return Objects.equals(find(e1), find(e2));
	}

	//region	private methods


	/**
	 * 往并查集里添加元素
	 *
	 * @param ele
	 */
	private void makeSet(E ele) {
		if (!parents.containsKey(ele)) {
			//TODO:定义好 默认的 parentNode = this
			parents.put(ele, new Node<>(ele));
		}
	}

	/**
	 * 查找 ele 的根节点
	 * 第一个要完成的方法
	 *
	 * @param ele
	 * @return
	 */
	private Node<E> node(E ele) {
		// 根节点
		Node<E> rootNode = parents.get(ele);
		//当根节点指向本节点时 -> 说明是终点
		while (!Objects.equals(rootNode, rootNode.parentNode)) {
			rootNode = rootNode.parentNode;
		}
		//find  root
		Node<E> curNode = parents.get(ele);
		E cur = ele;
		E prev = ele;

		//把 根节点写进去 -- 进行路径压缩
		while (!Objects.equals(curNode, curNode.parentNode)) {
			prev = cur;

			curNode = curNode.parentNode;
			cur = curNode.value;
			parents.put(prev, rootNode);
		}

		return rootNode;
	}

	//endregion

	/**
	 * 一般为了封装性，避免内部原理暴露
	 * equals 比较的是 value
	 * 这个对象的目的是：
	 * 1.存储 value ;
	 * 2.存储 rank;
	 * 3.存储 parent
	 * 那么明显，要获取 next 就要从 Node 去拿
	 */
	public static class Node<E> {
		/**
		 * 存储 元素的值
		 */
		public E value;
		/**
		 * 高度（秩）
		 */
		public int rank = 1;

		/**
		 * 父节点
		 */
		public Node<E> parentNode = null;

		//region	constructor

//		public Node(E value, Node<E> parentNode) {
//			this.value = value;
//			this.parentNode = parentNode;
//		}

		public Node(E value) {
			this.value = value;
			this.parentNode = this;
		}
		//endregion


		@Override
		public String toString() {
			return "value_" + value == null ? "null" : value.toString() + "rank_" + rank;
		}
	}
}
